#include  "ClasseNoArvoreBinaria.h"
#include  "ClasseArvoreBinaria.h"

//========== CONSTRUTOR ========================
Arvore::Arvore()
{
  raiz = NULL;
}
//========== CONSTRUTOR COM PALAVRA ============
Arvore::Arvore(String entrada)
{
  raiz = new NoArvore(entrada,1);
}
//========== DESTRUTOR ========================
Arvore::~Arvore()
{
  if(raiz != NULL)
  {
    delete raiz;
    raiz = NULL;
  }
}
//========== VERIFICA ARVORE VAZIA ===================
bool Arvore::empty()
{
  return (raiz == NULL);
}
//========== RETORNA RAIZ ==============================
NoArvore* Arvore::getRaiz()
{
  return raiz;
}
//===========PROCURA INDICE E RETORNA PONTEIRO =======
NoArvore* Arvore::getNo(int indice)
{
  NoArvore * resultado = NULL;
  if (!(empty()))
  {
    resultado = Procura(raiz, indice);
  }
  return (resultado);
}
//=========== METODO AUXILIAR DE GETNO ===============
NoArvore* Arvore::Procura(NoArvore* pont, int ind)
{
  NoArvore * resultado = pont;
  if ((pont!=NULL)&&((pont->getIndice())!=ind))
  {
     resultado = Procura(pont->getEsquerda(), ind);
     if (resultado == NULL)
     { resultado = Procura(pont->getDireita(), ind); }
  }
  return (resultado);
}
//============ INSERE ================================
int Arvore::insere(String word, int ind, bool lado)
{
  int indice;
  NoArvore* proc = getNo(ind);

  indice = 0;

  if(raiz == NULL)     // Arvore esta vazia.
    {
     indice = 1;
     raiz = new NoArvore(word, indice);
    }
  else                 // Arvore nao esta vazia.
    {
     if (proc!=NULL)
     {
       if ((proc->getEsquerda()==NULL) && (lado==true)) //verdadeiro: insere a esquerda
       {
         indice = (2*ind);
         NoArvore * novo = new NoArvore(word, indice);
         proc->setEsquerda(novo);
       }
       if ((proc->getDireita()==NULL) && (lado==false))  //falso: insere a direita
       {
         indice = ((2*ind)+1);
         NoArvore * novo = new NoArvore(word, indice);
         proc->setDireita(novo);
       }
     }
    }
  return (indice);
}
//============ REMOVE NO =============================
void Arvore::remove(int ind)
{
  NoArvore* proc = getNo(ind);
  NoArvore* pai;

  if (proc!=NULL)
  {
    if(proc == raiz)
      {
       delete(proc);
       raiz = NULL;
      }
    else
      {
       if ((ind%2)==0)
       {
         pai = getNo(ind/2);
         delete(proc);
         pai->setEsquerda(NULL);
       }
       else
       {
         pai = getNo((ind-1)/2);
         delete(proc);
         pai->setDireita(NULL);
       }
      }
    proc=NULL;
  }
}
//========== TAMANHO DA ARVORE =======================
int Arvore::tamanhoArvore()
{
  int maior, nivel;
  maior = nivel = 1;
  maior = maiorIndice(raiz,maior);
  while (maior>1)
  {
    if ((maior%2)==0) maior = maior/2;
    else maior = (maior-1)/2;

    nivel++;
  }
  return (nivel);
}
//========= PERCORRE, AUXILIAR DE TAMANHO ARVORE======
int Arvore::maiorIndice(NoArvore* pont, int ind)
{
  int resultado = ind;
  if (pont!=NULL)
  {
     if ((pont->getIndice())>resultado)
     {
       resultado = pont->getIndice();
     }
     resultado = maiorIndice(pont->getEsquerda(), resultado);
     resultado = maiorIndice(pont->getDireita(), resultado);
  }
  return (resultado);
}
//=========== RETORNA O NIVEL DE UM NO ===============
int Arvore::nivelNo(int ind)
{
  int retorno;
  retorno = 0;

  if(raiz != NULL)
    {
     retorno = Busca(raiz, ind);
     if(retorno > 0)
       {
        retorno--;
       }
    }
  return (retorno);
}
//=========== METODO AUXILIAR DE NIVELNO =============
int Arvore::Busca(NoArvore* pont, int ind)
{
  int retorno;
  retorno = 0;

  if(pont != NULL)
    {
     if(pont->getIndice() == ind)
       {
        retorno = 1;
       }
     else
       {
        retorno = Busca(pont->getEsquerda(), ind);
        if(retorno != 0)
          {
           retorno++;
          }
        else
          {
           retorno = Busca(pont->getDireita(), ind);
           if(retorno != 0)
             {
              retorno++;
             }
          }
       }
    }
  return (retorno);
}
//===========PROCURA INDICE E RETORNA TEXTO===========
String Arvore::getTexto(int indice)
{
  String retorno = "";
  NoArvore * resultado = NULL;

  if(! (empty()))
    {
     resultado = Procura(raiz, indice);
    }

  if(resultado != NULL)
    {
     retorno = resultado->getPalavra();
    }

  return (retorno);
}

